\documentclass{uicthesi}
\usepackage{newlfont}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{euler}

\def\new@fontshape#1#2#3#4#5{\expandafter
     \edef\csname#1/#2/#3\endcsname{\expandafter\noexpand
                                 \csname #4\endcsname}}
\new@fontshape{cmr}{bx}{sc}{
      <5>cmcsc8 at 5pt%
      <6>cmcsc8 at 6pt%
      <7>cmcsc8 at 7pt%
      <8>cmcsc8%
      <9>cmcsc9%
      <10>cmcsc10%
      <11>cmcsc10 at 10.95pt%
      <12>cmcsc10 at 12pt%
      <14>cmcsc10 at 14.4pt%
      <17>cmcsc10 at 17.28%
      <20>cmcsc10 at 20.736pt%
      <25>cmcsc10 at 24.8832pt%
      }{}
\mathversion{normal}
\newcommand{\ams}{{$\cal{A}\cal{M}\cal{S}$}}
\newcommand{\amslatex}{{$\cal{A}\cal{M}\cal{S}$-\LaTeX{}}}
\newcommand{\amstex}{{$\cal{A}\cal{M}\cal{S}$-\TeX{}}}
\newcommand{\BibTeX}{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
\newcommand{\uicthesi}{{$\mathbb{UICTHESI}$}}
 
\newcommand\bs{\char '134 }   % A backslash character for \tt font
\newcommand{\lb}{\char '173 } % A left brace character for \tt font
\newcommand{\rb}{\char '175 } % A right brace character for \tt font
 

%%%%%%%%        DO NOT TOUCH ABOVE THIS      %%%%%%%%%%%%%%% 

% one or two other commands
\def\newfont#1#2{\@ifdefinable #1{\font #1=#2\relax}}
\def\symbol#1{\char #1\relax}



\title{A Study Of Performance Characteristics Social Network Applications on Clusters Using MPI}
\author{Harish Ganapati Naik}
\pdegrees{of the\\University of Illinois at Chicago}
\degree{Master of Science in Computer Science}
 
\begin{document}
\maketitle
\copyrightpage
\dedication
\begin{center}
\vspace{20cm}
Dedicated to my parents.
\end{center} 
\acknowledgment
I would like to thank my advisor Dr. Mitchell Theys for guiding me through my research. I like to thank my parents, sister, friends and all my teachers.

\initials{HGN}
 
\preface
This is the default preface. Put some content here.
 
\tableofcontents
\listoftables
\listoffigures
 
\listofabbreviations
\begin{list}
{}
{\setlength
   {\labelwidth}{1in}
    \setlength{\leftmargin}{1.5in}
    \setlength{\labelsep}{.5in}
    \setlength{\rightmargin}{\leftmargin}}
\item[AMS\hfill] American Mathematical Society
\item[CTAN\hfill] Comprehensive \TeX\ Archive Network
\item[TUG\hfill] \TeX\ Users Group
\item[UIC\hfill] University of Illinois at Chicago
\item[UICTHESI\hfill] Thesis formatting system for use at UIC.
\end{list}
 
\summary
Community identification in dynamic social networks is a very compute intense problem. Hence they require huge amounts of computing power. We have tried to parallelize the algorithm for better performance. 
\chapter{Introduction}
\section{Preliminaries}

Identifying communities using optimal coloring techniques is  NP hard. \cite{tanthipanandh07-community} presents heuristic algorithms that find near optimal solutions in practice. The algorithm suggested runs on a uni-processor system. On larger data sets it takes a long times for computation.

We present an algorithm for cluster implementation of the algorithm for faster computation.

\section{Problem Formulation}
The algorithm for community identification in dynamic social networks utilizes a exhaustively generated set of colorings. The number of colorings generated thus is of an exponential order. The cost function is applied iteratively to each of the colorings. This results of a huge running time cost.

We observe that once the coloring set is generated, the computation of one coloring is independent of other. In such a case, it is possible to isolate a part of computation performed on each of these colorings to separate individual processes or computing units. 

\chapter{Group Coloring Heuristics}
 
 \section{Time and Space Complexity}
 \section{Number of Colors}
 
 \chapter{Parallelization}
The solution to the problem has an exponential growth time. It is observed that the cost calculation function using the recursive procedure is the most time consuming. The number of coloring instances exhaustively generated is given by:

\begin{math}
fact(maxColor)^{numberOfTimeSteps - 1}

Hence the cost computation function has a complexity of:
fact(maxColor)^{(numberOfTimeSteps - 1} x NumIndividuals x numTimeSteps 
\end{math}
\section{Message Passing Interface}
MPI is a library standard for programming on clusters. Parsoc has been developed using the MPICH2. MPICH2 is an MPI implementation from Argonne National Laboratory.

\chapter{Hardware and Platform}
\section{Cluster}
\subsection{Thunder}
 \chapter{Experimental Results}
 
 \chapter{Conclusion}
 \section{Future Work}
 The current application has been written using MPI and tested on platforms using mpich2 based cluster running NFS. It does not make use of clusters consisting of nodes with multicore processors. The application needs to be ported to the open MP platform and test it on multiprocessors machines. The application can be ported to run on a cluster built with multicore GPU.
 
\appendices
\appendix
\newpage
%\input fontsym
\bibformb
\bibliography{parsoc}
\vita
This is where the vita goes.  Its organization is left as an exercise.
Hint: see the list of abbreviations.
\end{document}
